package com.lx.algorithm.Tree;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * Description: 判断一棵树是否是完全二叉树
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-10-18 14:42:44
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-10-18     张李鑫                     1.0         1.0 Version
 */
public class IsCBT {
    static class Node<T> {
        T value;
        Node left;
        Node right;

        public Node(T value) {
            this.value = value;
        }
    }

    /**
     * 判断一棵树是否是完全二叉树：
     * 一棵树每层的节点都是满的
     * 如果不满只能是最后一层不满 并且最后一层与全满树的位置一一对应
     * <p>
     * <p>
     * 按层遍历 当遇到一个节点不同时拥有左右节点的时候 接下来每次遍历的节点都不能拥有左右节点
     */
    public static boolean isCBT1(Node node) {
        if (node == null) {
            return true;
        }
        boolean flag = false;
        Queue<Node> list = new LinkedList<>();
        list.add(node);
        while (!list.isEmpty()) {
            Node cur = list.poll();
            if (flag && (cur.left != null || cur.right != null)) {
                return false;
            }
            if (cur.right != null && cur.left == null) {
                return false;
            }
            if (cur.left == null || cur.right == null) {
                flag = true;
            }
            if (cur.left != null) {
                list.add(cur.left);
            }
            if (cur.right != null) {
                list.add(cur.right);
            }
        }
        return true;
    }

    public static class Info {
        public int height;
        public boolean isCBT;
        public boolean isFull;

        public Info(int height, boolean isCBT, boolean isFull) {
            this.height = height;
            this.isCBT = isCBT;
            this.isFull = isFull;
        }
    }

    public static boolean isCBT(Node head) {
        return process(head).isCBT;
    }

    public static Info process(Node node) {

        return null;
    }

}
